import java.util.ArrayList;

public class Board
{
	Tile[][] board = new Tile[6][6];

	ArrayList<Block> blocks = new ArrayList<Block>();
	
	static int timesIveBeenKilled = 0;
	
	static int IDexcount; // number of expanded nodes by ID
	
	public Board()
	{
		/*if(!putMouse())
			System.out.println("ERROR NO MOUSE !!!!");

		if(!Insert(new Block(3, false, 0, 4)))
			System.out.println("No!!!");*/
	}

	
	static public Board generateBoard(Board b, Action a) throws Exception
	{
		Board x = new Board();
		
		for(Block blo : b.blocks)
		{
			Block tmp = new Block(blo.size,blo.horizontal,blo.x,blo.y);
			
			if( blo instanceof Mouse)
			{
				Mouse m = new Mouse(blo.y,blo.y+1);
				x.Insert(m);
			}
			else
				x.Insert(tmp);
		}
		
		if(!x.move(x.blocks.get(a.block), a.direction))
		{
			System.out.println("Kill me " + timesIveBeenKilled);
			x.print();
			System.out.println(a.block + " the action " + a.direction);
			timesIveBeenKilled++;
		}
		
		return x;
	}

	

	static Solution MIM(SearchProblem problem, String strategy, boolean visualize)
	{
		if(strategy.equals("BF"))
			return BF(problem,visualize);
		
		if(strategy.equals("DF"))
			return DF(problem,visualize);
		
		if(strategy.equals("ID"))
			return ID(problem,visualize);
		
		if(strategy.startsWith("GR"))
			return GR(problem,visualize,strategy.charAt(2));
		
		if(strategy.startsWith("AS"))
			return AS(problem,visualize,strategy.charAt(2));
		
		return null;
	}
	
	
	private static Solution AS(SearchProblem problem, boolean visualize,  char heuristic)
	{
		int expandedNodes = 0;
		
		ArrayList<Node> nodes = new ArrayList<Node>();
		
		nodes.add(new Node(problem.initState,Integer.parseInt(heuristic+"")));
		
		ArrayList<Action> actions;
		
		while(!nodes.isEmpty())
		{
			if(problem.isGoal(nodes.get(aStar(nodes))))
			{
				Node tmp = nodes.get(aStar(nodes));
				ArrayList<Action> sol = new ArrayList<Action>();
				
				if(tmp.depth == 0)
				{
					if(visualize)
						tmp.state.print();
					return new Solution(null,0,0);
				}
				
				while(tmp.depth != 0)
				{
					sol.add(0, tmp.action);
					tmp = tmp.parentNode;
				}
				
				if(visualize)
					showSteps(sol,problem.initState);
					System.out.println("The number of expanded nodes is "+expandedNodes);
					System.out.println("The cost of the solution is "+sol.size());
				return new Solution(sol,sol.size(),expandedNodes);
			}
			else // not goal
			{
				Node expandThis = nodes.remove(aStar(nodes));
				actions = expandThis.state.getActions();
				expandedNodes++;
				
				for(Action action:actions)
				{
					Node x = new Node(expandThis, action,Integer.parseInt(heuristic+""));
					nodes.add(x);
				}
			}
		}
		
		return null;
	}

	private static int aStar(ArrayList<Node> nodes)
	{
		int leastHueristiCostIndex = 0;
		Node leastHeuristiCost = nodes.get(0); 
		
		for(int i =0 ; i < nodes.size() ;i++)
		{
			if(nodes.get(i).heuristiCost < leastHeuristiCost.heuristiCost)
			{
				leastHeuristiCost = nodes.get(i);
				leastHueristiCostIndex = i;
			}
		}
		
		return leastHueristiCostIndex;
	}


	private static Solution GR(SearchProblem problem, boolean visualize, char heuristic)
	{
		int expandedNodes = 0;
		
		ArrayList<Node> nodes = new ArrayList<Node>();
		
		nodes.add(new Node(problem.initState,Integer.parseInt(heuristic+"")));
		
		ArrayList<Action> actions;
		
		while(!nodes.isEmpty())
		{
			if(problem.isGoal(nodes.get(greedyH(nodes))))
			{
				Node tmp = nodes.get(greedyH(nodes));
				ArrayList<Action> sol = new ArrayList<Action>();
				
				if(tmp.depth == 0)
				{
					if(visualize)
						tmp.state.print();
					return new Solution(null,0,0);
				}
				
				while(tmp.depth != 0)
				{
					sol.add(0, tmp.action);
					tmp = tmp.parentNode;
				}
				
				if(visualize)
					showSteps(sol,problem.initState);
				
				System.out.println("The number of expanded nodes is "+expandedNodes);
				System.out.println("The cost of the solution is "+sol.size());
				
				return new Solution(sol,sol.size(),expandedNodes);
			}
			else // not goal
			{
				Node expandThis = nodes.remove(greedyH(nodes));
				actions = expandThis.state.getActions();
				expandedNodes++;
				
				for(Action action:actions)
				{
					Node x = new Node(expandThis, action,Integer.parseInt(heuristic+""));
					nodes.add(x);
				}
			}
		}
		
		return null;
	}

	private static int greedyH(ArrayList<Node> nodes)
	{
		int leastHueristicIndex = 0;
		Node leastHeuristic = nodes.get(0); 
		
		for(int i =0 ; i < nodes.size() ;i++)
		{
			if(nodes.get(i).heuristic < leastHeuristic.heuristic)
			{
				leastHeuristic = nodes.get(i);
				leastHueristicIndex = i;
			}
		}
		
		return leastHueristicIndex;
	}

	
	private static Solution ID(SearchProblem problem, boolean visualize)
	{
		IDexcount = 0;
		
		for(int i =0; ;i++)
		{
			Solution sol = DFL(problem,visualize,i);
			if(sol == null)
				continue;
			else
			{
				if(visualize)
					showSteps(sol.actions,problem.initState);
					System.out.println("The number of expanded nodes is "+IDexcount);
					System.out.println("The cost of the solution is "+sol.cost);
				return sol;
			}
		}
	}
	
	
	static Solution DFL(SearchProblem problem, boolean visualize, int limit)
	{
		ArrayList<Node> nodes = new ArrayList<Node>();
		nodes.add(new Node(problem.initState));
		ArrayList<Action> actions;
		
		while(!nodes.isEmpty())
		{
			if(problem.isGoal(nodes.get(nodes.size()-1)))
			{
				Node tmp = nodes.get(nodes.size()-1);
				ArrayList<Action> sol = new ArrayList<Action>();
				
				if(tmp.depth == 0)
					return new Solution(null,0,0);
				
				while(tmp.depth != 0)
				{
					sol.add(0, tmp.action);
					tmp = tmp.parentNode;
				}
				
				return new Solution(sol,sol.size(),IDexcount);
			}
			else // not goal
			{
				Node expandThis = nodes.remove(nodes.size()-1);
				
				if(expandThis.depth==limit)
					continue;
					
				actions = expandThis.state.getActions();
				IDexcount++;
				
				for(Action action:actions)
				{
					Node x = new Node(expandThis, action);
					nodes.add(x);
				}
			}
		}
		
		return null;
	}
	
	
	private static Solution DF(SearchProblem problem, boolean visualize)
	{
		int expandedNodes = 0;
		
		ArrayList<Node> nodes = new ArrayList<Node>();
		
		nodes.add(new Node(problem.initState));
		
		ArrayList<Action> actions;
		
		while(!nodes.isEmpty())
		{
			if(problem.isGoal(nodes.get(nodes.size()-1)))
			{
				Node tmp = nodes.get(nodes.size()-1);
				ArrayList<Action> sol = new ArrayList<Action>();
				
				if(tmp.depth == 0)
				{
					if(visualize)
						tmp.state.print();
					return new Solution(null,0,0);
				}
					
				
				while(tmp.depth != 0)
				{
					sol.add(0, tmp.action);
					tmp = tmp.parentNode;
				}
				
				if(visualize)
					showSteps(sol,problem.initState);
					System.out.println("The number of expanded nodes is "+expandedNodes);
					System.out.println("The cost of the solution is "+sol.size());
				
				return new Solution(sol,sol.size(),expandedNodes);
			}
			else // not goal
			{
				Node expandThis = nodes.remove(nodes.size()-1);
				actions = expandThis.state.getActions();
				expandedNodes++;
				
				for(Action action:actions)
				{
					Node x = new Node(expandThis, action);
					nodes.add(x);
				}
			}
		}
		
		return null;
	}

	
	static Solution BF(SearchProblem problem, boolean visualize)
	{
		int expandedNodes = 0;
		
		ArrayList<Node> nodes = new ArrayList<Node>();
		
		nodes.add(new Node(problem.initState));
		
		ArrayList<Action> actions;
		
		while(!nodes.isEmpty())
		{
			if(problem.isGoal(nodes.get(0)))
			{
				Node tmp = nodes.get(0);
				ArrayList<Action> sol = new ArrayList<Action>();
				
				if(tmp.depth == 0)
				{
					if(visualize)
						tmp.state.print();
					return new Solution(null,0,0);
				}
				
				while(tmp.depth != 0)
				{
					sol.add(0, tmp.action);
					tmp = tmp.parentNode;
				}
				
				if(visualize)
					showSteps(sol,problem.initState);
					System.out.println("The number of expanded nodes is "+expandedNodes);
					System.out.println("The cost of the solution is "+sol.size());

					return new Solution(sol,sol.size(),expandedNodes);
			}
			else // not goal
			{
				Node expandThis = nodes.remove(0);
				actions = expandThis.state.getActions();
				expandedNodes++;
				
				for(Action action:actions)
				{
					Node x = new Node(expandThis, action);
					nodes.add(x);
				}
			}
		}
		
		return null;
	}
	
	
	
	private static void showSteps(ArrayList<Action> sol, Board initState)
	{
		initState.print();
		
		if(sol.size()==0)
			return;
		
		for(Action action : sol)
		{
			initState.move(initState.blocks.get(action.block), action.direction);
			initState.print();
		}
	}

	boolean putMouse()
	{
		Mouse mouse = new Mouse(0,1);
		if(Insert(mouse))
			return true;
		else
			return false;
	}

	
	
	boolean Insert(Block t)
	{
		try
		{
			int x = t.x;
			int y = t.y;

			if(board[x][y] != null)
				System.out.println("el 7ayah morrah");

			if(t.horizontal)
			{
				if(board[x][y + 1] == null)
				{
					board[x][y] = t.tiles.get(0);
					board[x][y + 1] = t.tiles.get(1);
					blocks.add(t);
					return true;
				} else
					return false;
			} else
			// vertical
			{
				if(board[x + 1][y] == null)
				{
					if(t.size == 2 && board[x + 1][y] == null)
					{
						board[x][y] = t.tiles.get(0);
						board[x + 1][y] = t.tiles.get(1);
						blocks.add(t);
						return true;
					} else if(t.size == 3 && board[x + 2][y] == null)
					{
						board[x][y] = t.tiles.get(0);
						board[x + 1][y] = t.tiles.get(1);
						board[x + 2][y] = t.tiles.get(2);
						blocks.add(t);
						return true;
					} else
						return false;
				} else
					return false;
			}
		} catch( Exception e)
		{
			return false;
		}

	}
	
	
	
	void moveit(Block b, char d)
	{
		switch(d)
		{
			case 'u':
			case 'd':
			case 'r':
			case 'l':
		}
	}

	
	
	boolean move(Block block, char direction)
	{
		switch(direction)
		{
		case 'u':
			if(block.horizontal)
				return false;
			else // vertical block
			{
				if(block.x-1  >= 0 )
				{
					if(board[block.x-1][block.y]==null)
					{
						for(Tile t : block.tiles)
							t.x -= 1;
						
						board[block.x-1][block.y] = board[block.x][block.y];
						board[block.x][block.y] = board[block.x+1][block.y];
						if(block.size==3)
						{
							board[block.x+1][block.y] = board[block.x+2][block.y];
							board[block.x+2][block.y] = null;
							block.x -=1;
							return true;
						}
						else
						{
							board[block.x+1][block.y] = null;
							block.x -=1;
							return true;
						}
							
					}
					else return false;
				}
				else return false; //block starts at zero can't move up
			}
		case 'd':
			if(block.horizontal)
				return false;
			else // vertical block
			{
				if(block.x+block.size  <= 5 )
				{
					if(board[block.x+block.size][block.y]==null)
					{
						for(Tile t : block.tiles)
							t.x += 1;
						
						board[block.x+block.size  ][block.y] = board[block.x+block.size-1][block.y];
						board[block.x+block.size-1][block.y] = board[block.x+block.size-2][block.y];
						if(block.size==3)
						{
							board[block.x+block.size-2][block.y] = board[block.x][block.y];
							board[block.x][block.y] = null;
							block.x +=1;
							return true;
						}
						else {
							board[block.x+block.size-2][block.y] = null;
							block.x +=1;
							return true;
						}
							
					}
					else return false;
				}
				else return false; //block starts at zero can't move up
			}
		case 'r':
			if(!block.horizontal)
				return false;
			else // vertical block
			{
				if(block.y+2  <= 5 )
				{
					if(board[block.x][block.y+2]==null)
					{
						for(Tile t : block.tiles)
							t.y += 1;
						
						board[block.x][block.y+2] = board[block.x][block.y+1];
						board[block.x][block.y+1] = board[block.x][block.y];
						board[block.x][block.y] = null;
						block.y +=1;
						return true;
					}
					else return false;
				}
				else return false; //block starts at zero can't move up
			}
			
		case 'l':
			if(!block.horizontal)
				return false;
			else // vertical block
			{
				if(block.y-1 >= 0 )
				{
					if(board[block.x][block.y-1]==null)
					{
						for(Tile t : block.tiles)
							t.y -= 1;
						
						board[block.x][block.y-1] = board[block.x][block.y];
						board[block.x][block.y] = board[block.x][block.y+1];
						board[block.x][block.y+1] = null;
						block.y -=1;	
						return true;
					}
					else return false;
				}
				else return false; //block starts at zero can't move up
			}
		}
		return false;
	}
	
	
	
	Block getBlock(Tile t)
	{
		Block returnable = null;
		for(Block b : blocks)
		{
			if(b.tiles.contains(t)) 
				returnable = b;
		}
		return returnable;
	}
	
	
	
	void print()
	{
		System.out.println("=========================");

		for(int i = 0; i < 6; i++)
		{
			for(int j = 0; j < 6; j++)
			{
				if(board[i][j] == null)
					System.out.print("|   ");
				else
				{
					if(getBlock(board[i][j]) instanceof Mouse)
						System.out.print("|  M");
					else if(getBlock(board[i][j]).horizontal)
						System.out.print("|H" + board[i][j].x + "" + board[i][j].y);
					else
						// vertical
						System.out.print("|V" + board[i][j].x + "" + board[i][j].y);
				}

			}
			System.out.println("| ");
		}

		System.out.println("=========================");
	}
	
	
	
	ArrayList<Action> getActions()
	{
		ArrayList<Action> actions = new ArrayList<Action>();
		
		for(int i = 0; i < blocks.size() ;i++)
		{
			if(blocks.get(i).horizontal)
			{
				
				if(move(blocks.get(i), 'l'))
				{
					move(blocks.get(i), 'r');
					actions.add(new Action(i,'l'));
				}
				
				if(move(blocks.get(i), 'r'))
				{
					move(blocks.get(i), 'l');
					actions.add(new Action(i,'r'));
				}
			}
			else // vertical
			{
				if(move(blocks.get(i), 'u'))
				{
					move(blocks.get(i), 'd');
					actions.add(new Action(i,'u'));
				}
				
				if(move(blocks.get(i), 'd'))
				{
					move(blocks.get(i), 'u');
					actions.add(new Action(i,'d'));
				}
			}
		}
		
		return actions;
	}
	
	
	
 	public static void main(String[] args)
	{
		Board s = new Board();
	
		s.putMouse();
		
		s.Insert(new Block(3, false, 0, 4));
		
		s.Insert(new Block(2, true, 3, 4));
		
		MouseinaMaze mm = new MouseinaMaze(s);
		
		Solution sol = MIM(mm,"AS1",false);
		
		sol.cost ++;
		sol.cost --;
	}
	
}
